Relational model

 ( 1969 In Computing ) 

The definition of a tuple allows for a unique empty tuple with no values, corresponding to the empty set of attributes. If a relation has a degree of 0 (i.e. its heading contains no attributes), it may have either a cardinality of 0 (a body containing no tuples) or a cardinality of 1 (a body containing the single empty tuple). These relations represent Boolean domain truth values. The relation with degree 0 and cardinality 0 is False, while the relation with degree 0 and cardinality 1 is True.

OrderInvoice ('''Order ID''', '''Invoice ID''')
     

Our first definition concerns the notion of tuple, which formalizes the notion of row or record in a table:

Tuple

A tuple is a partial function from attribute names to atomic values.

Header

A header is a finite set of attribute names.

Projection

The projection of a tuple $t$ on a finite set of attributes $A$ is $tA\; =\; \backslash \{\; (a,\; v)\; :\; (a,\; v)\; \backslash in\; t,\; a\; \backslash in\; A\; \backslash \}$.

The next definition defines relation that formalizes the contents of a table as it is defined in the relational model.

Relation

A relation is a tuple $(H,\; B)$ with $H$, the header, and $B$, the body, a set of tuples that all have the domain $H$.

Such a relation closely corresponds to what is usually called the extension of a predicate in first-order logic except that here we identify the places in the predicate with attribute names. Usually in the relational model a logical schema is said to consist of a set of relation names, the headers that are associated with these names and the constraints that should hold for every instance of the database schema.

Relation universe

A relation universe $U$ over a header $H$ is a non-empty set of relations with header $H$.

Relation schema

A relation schema $(H,\; C)$ consists of a header $H$ and a predicate $C(R)$ that is defined for all relations $R$ with header $H$. A relation satisfies a relation schema $(H,\; C)$ if it has header $H$ and satisfies $C$.

Superkey

A superkey is written as a finite set of attribute names.

A superkey $K$ holds in a relation $(H,\; B)$ if:

* $K\; \backslash subseteq\; H$ and

* there exist no two distinct tuples $t\_1,\; t\_2\; \backslash in\; B$ such that $t\_1K\; =\; t\_2K$.

A superkey holds in a relation universe $U$ if it holds in all relations in $U$.

Theorem: A superkey $K$ holds in a relation universe $U$ over $H$ if and only if $K\; \backslash subseteq\; H$ and $K\; \backslash rightarrow\; H$ holds in $U$.

Candidate key

A superkey $K$ holds as a candidate key for a relation universe $U$ if it holds as a superkey for $U$ and there is no proper subset of $K$ that also holds as a superkey for $U$.

Functional dependency

A functional dependency (FD for short) is written as $X\; \backslash rightarrow\; Y$ for $X,\; Y$ finite sets of attribute names.

A functional dependency $X\; \backslash rightarrow\; Y$ holds in a relation $(H,\; B)$ if:

* $X,\; Y\; \backslash subseteq\; H$ and

* $\backslash forall$ tuples $t\_1,\; t\_2\; \backslash in\; B$, $t\_1X\; =\; t\_2X~\backslash Rightarrow~t\_1Y\; =\; t\_2Y$

A functional dependency $X\; \backslash rightarrow\; Y$ holds in a relation universe $U$ if it holds in all relations in $U$.

Trivial functional dependency

A functional dependency is trivial under a header $H$ if it holds in all relation universes over $H$.

Theorem: An FD $X\; \backslash rightarrow\; Y$ is trivial under a header $H$ if and only if $Y\; \backslash subseteq\; X\; \backslash subseteq\; H$.

Closure

Armstrong's axioms: The closure of a set of FDs $S$ under a header $H$, written as $S^+$, is the smallest superset of $S$ such that:

* $Y\; \backslash subseteq\; X\; \backslash subseteq\; H~\backslash Rightarrow~X\; \backslash rightarrow\; Y\; \backslash in\; S^+$ (reflexivity)

* $X\; \backslash rightarrow\; Y\; \backslash in\; S^+\; \backslash land\; Y\; \backslash rightarrow\; Z\; \backslash in\; S^+~\backslash Rightarrow~X\; \backslash rightarrow\; Z\; \backslash in\; S^+$ (transitivity) and

* $X\; \backslash rightarrow\; Y\; \backslash in\; S^+\; \backslash land\; Z\; \backslash subseteq\; H~\backslash Rightarrow~(X\; \backslash cup\; Z)\; \backslash rightarrow\; (Y\; \backslash cup\; Z)\; \backslash in\; S^+$ (augmentation)

Theorem: Armstrong's axioms are sound and complete; given a header $H$ and a set $S$ of FDs that only contain subsets of $H$, $X\; \backslash rightarrow\; Y\; \backslash in\; S^+$ if and only if $X\; \backslash rightarrow\; Y$ holds in all relation universes over $H$ in which all FDs in $S$ hold.

Completion

The completion of a finite set of attributes $X$ under a finite set of FDs $S$, written as $X^+$, is the smallest superset of $X$ such that:

* $Y\; \backslash rightarrow\; Z\; \backslash in\; S\; \backslash land\; Y\; \backslash subseteq\; X^+~\backslash Rightarrow~Z\; \backslash subseteq\; X^+$

The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.

Theorem: Given a set $S$ of FDs, $X\; \backslash rightarrow\; Y\; \backslash in\; S^+$ if and only if $Y\; \backslash subseteq\; X^+$.

Irreducible cover

An irreducible cover of a set $S$ of FDs is a set $T$ of FDs such that:

* $S^+\; =\; T^+$

* there exists no $U\; \backslash subset\; T$ such that $S^+\; =\; U^+$

* $X\; \backslash rightarrow\; Y\; \backslash in\; T~\backslash Rightarrow\; Y$ is a singleton set and

* $X\; \backslash rightarrow\; Y\; \backslash in\; T\; \backslash land\; Z\; \backslash subset\; X~\backslash Rightarrow~Z\; \backslash rightarrow\; Y\; \backslash notin\; S^+$.

'''algorithm''' derive candidate keys from functional dependencies '''is'''
    '''input:''' a set ''S'' of FDs that contain only subsets of a header ''H''
    '''output:''' the set ''C'' of superkeys that hold as candidate keys in
            all relation universes over ''H'' in which all FDs in ''S'' hold
     

    ''C'' := ∅         // found candidate keys
    ''Q'' := { ''H'' }      // superkeys that contain candidate keys
    '''while''' ''Q'' <> ∅ '''do'''
        let ''K'' be some element from ''Q''
        ''Q'' := ''Q'' – { ''K'' }
        ''minimal'' := '''true'''
        '''for each''' ''X->Y'' '''in''' ''S'' '''do'''
            ''K' '':= (''K'' – ''Y'') ∪ ''X''   // derive new superkey
            '''if''' ''K' ''⊂ ''K'' '''then'''
                ''minimal'' := '''false'''
                ''Q'' := ''Q'' ∪ { ''K' ''}
            '''end if'''
        '''end for'''
        '''if''' ''minimal'' '''and''' there is not a subset of ''K'' in ''C'' '''then'''
            remove all supersets of ''K'' from ''C''
            ''C'' := ''C'' ∪ { ''K'' }
        '''end if'''
    '''end while'''
     

Datalog is a database definition language, which combines a relational view of data, as in the relational model, with a logical view, as in logic programming. Whereas relational databases use a relational calculus or relational algebra, with relational operations, such as union, intersection, set difference and cartesian product to specify queries, Datalog uses logical connectives, such as if, or, and and not to define relations as part of the database itself.

In contrast with the relational model, which cannot express recursive queries without introducing a least-fixed-point operator,Aho, A.V. and Ullman, J.D., 1979, January. Universality of data retrieval languages. In Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (pp. 110-119). recursive relations can be defined in Datalog, without introducing any new logical connectives or operators.

• Domain relational calculus
• List of relational database management systems
• Query language
• Database query language
• Information retrieval query language
• Relation
• Relational database
• Relational database management system
• Tuple-versioning

• (2025). 9780201709285, Addison-Wesley. ISBN 9780201709285
• C. J. Date (2025). 9780321197849, Pearson Education. . ISBN 9780321197849

• cited in Codd's 1970 paper.
• .
• .
• .